package 链表.两两交换链表中的节点;

import java.util.Stack;
/**
 * 题目描述：
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
 * 你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换）。
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 * 力扣地址：https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 * 力扣题：24
 * */
/**
 * 复杂度分析
 *
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 * */
/**
 * 解题思路：
 * 交换相邻节点，你就可以想到改变指针方向即可
 * 然后创建一个虚拟节点
 * 指向-》2-》1-》3-》4
 * 画图好做,这是原来的链表，现在要两辆交换
 * 1 -> 2 -> 3 -> 4
 * 定义虚拟节点为cur
 * cur -> 2 -> 1这样不就改变指针实现交换了吗
 * 然后完整就是
 * cur -> 2 -> 1 -> 3 -> 4
 * 然后虚拟节点进一位进到头结点，头结点也进一位
 * 继续上述流程，知道交换完毕
 * */

// 虚拟头结点
class Solution {
    public ListNode swapPairs(ListNode head) {

        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode prev = dummyNode;

        while (prev.next != null && prev.next.next != null) {
            ListNode temp = head.next.next; // 缓存 next
            prev.next = head.next;          // 将 prev 的 next 改为 head 的 next
            head.next.next = head;          // 将 head.next(prev.next) 的next，指向 head
            head.next = temp;               // 将head 的 next 接上缓存的temp
            prev = head;                    // 步进1位
            head = head.next;               // 步进1位
        }
        return dummyNode.next;
    }
}

